            BOI.6. (Reea de calculatoare). Se dorete legarea n reea a n calcula-
toare (2n10). Problema const[ n obinerea unei reele liniare n care fiecare
calculator este legat exact de alte dou[ calculatoare, exceptnd calculatoarele din
capete, care au o singur[ leg[tur[. De exemplu, n desenul de mai jos calculatoa-
rele sunt identificate prin coordonatele lor (relativ la un sistem de axe neprecizat).
           Scopul problemei const[ n minimizarea lungimii cablului folosit; se cere
deci determinarea unui mod optim de reconectare al calculatoarelor n linie astfel
nct cablul folosit s[ aib[ lungimea minim[. Necesarul de cablu pentru a lega
direct dou[ calculatoare este egal cu distana dintre acestea, la care se adaug[ 10
m de cablu, utilizai pentru conexiuni anexe.

Intrare: Fiierul de intrare va reprezenta un set de date. Prima linie const[ dintr-un
singur num[r n (num[rul de calculatoare). In continuare, pe n linii succesive se dau
coordonatele fiec[rui calculator sub forma unei perechi de numere ntregi (din
intervalul [0,100]) separate prin cel puin un spaiu. De exemplu:
5
8 11
8 16
12 16
13 8
24 10
In acest caz reeaua are forma grafic[ prezentat[ mai sus, iar modul optim de
reconectare al calculatoarelor este:

Ieirea const[ din n linii. Pe prima linie se va da lungimea total[ a cablului.
Fiecare din celelalte linii este format[ din trei numere l,s,e avnd semnificaia:
lungimea l a cablului este necesar[ leg[rii directe a calculatoarelor definite la
intrare pe liniile s respectiv e. Ordinea de parcurgere a reelei este arbitrar[.
Pentru reeaua din exemplu ieirea va fi:
66.01
14     3 2
15     2 1
15.83  1 4
21.18  4 5
=============================================
          BOI 6 (Iuliu Vasilescu):
           Este o problem[ clasic[ de aflare a unui drum hamiltonian minim (Cornelia
Ivasc, Mona Pruna, Bazele Informaticii clasa X, Editura Petrion 1995).
program retea;
const nmax=10;
var i,j,n:integer;
    a:array[1..nmax,1..2] of real;
    b:array[1..nmax,1..nmax] of real;
    c,cm,d:array[1..nmax] of integer;
    l,lm:real;
    f:text;
---------------------------------------------------
procedure rec(p:integer);
  {genereaza recursiv si optimizat drumurile posibile; in "c"
se retine drumul curent; in "cm" drumul minim pana la pasul
curent; in "d" varfurile folosite pana la pasul curent; analog
in "l" si "lm" lungimea curenta si lungimea minima}
var i:integer;
begin
  if (l<lm)or(lm=0) then 
     begin
       if p>n then 
         begin
           if (l<lm)or(lm=0) then begin cm:=c;lm:=l; end;
         end 
              else
     if p=1 then
        for i:=1 to n do 
          begin
            c[1]:=i;d[i]:=1;rec(2);d[i]:=0;
          end
                    else
     for i:=1 to n do if d[i]=0 then 
        begin
          c[p]:=i;d[i]:=1;l:=l+b[c[p-1],i];
          rec(p+1);
          l:=l-b[c[p-1],i];d[i]:=0;
        end;
   end;
end;
-----------------------------------------------------
begin { Programul principal }
   assign(f,'in_pl2.txt');reset(f);
   read(f,n);
   for i:=1 to n do read(f,a[i,1],a[i,2]);
{se calculeaza distantele dintre noduri}
   for i:=1 to n-1 do for j:=i+1 to n do 
      begin
      b[i,j]:=sqrt((a[i,1]-a[j,1])*(a[i,1]-a[j,1])+
         (a[i,2]-a[j,2])*(a[i,2]-a[j,2]))+10;
         b[j,i]:=b[i,j];
      end;
{se initializeaza variabilele si se lanseaza procedura
recursiva}
   lm:=0;l:=0;
   for i:=1 to n do d[i]:=0;
   rec(1);
{se afiseaza rezultatele in formatul cerut}
   writeln('Rezultate:');writeln(lm:7:2);
   for i:=1 to n-1 do
writeln(b[cm[i],cm[i+1]]:7:2,cm[i]:3,cm[i+1]:3);
end.
------------------------------------------
Solutia 2 (Vlad Atanasiu)
uses crt;
type numar=array[1..101] of byte;
     punct=record
                 x,y:integer;
           end;
var c:array[1..100,1..100] of real;
    s:array[1..100] of boolean;
    solutie,solutie_finala:numar;
    drum_minim,minim,maxim:real;
  pozitie,poz_finala,nod_curent,nod_apropiat,
          nc,i,j,n:integer;
---------------------------------------------------------
procedure citeste;
{ citeste datele de intrare din fisierul 'input50' }
var t:text;
    i,j:integer;
    coordonate:array[1..100] of punct;
begin
   assign(t,'input50'); 
{ datele se citesc din fisierul 'input50' }
   reset(t); readln(t,n);
   for i:=1 to n do
      begin
        read(t,coordonate[i].x);
        readln(t,coordonate[i].y);
     end;
   for i:=1 to n do   
{Se determina matricea C a drumurilor}
   for j:=i+1 to n do
      begin
        c[i,j]:=sqrt(sqr(coordonate[i].x-coordonate[j].x)+
                   sqr(coordonate[i].y-coordonate[j].y));
        c[j,i]:=c[i,j];
      end;
   close(t);
end;
---------------------------------------------------------
function min(x,y:real):real;
begin
   min:=y;
   if y>x then min:=x;
end;
---------------------------------------------------------
begin { Programul principal }
   clrscr;
   citeste; drum_minim:=1500;
   for nc:=1 to n do
      begin
        nod_curent:=nc;
        for i:=1 to n do s[i]:=true;
        solutie[1]:=nod_curent; s[nod_curent]:=false;
        for i:=2 to n do
          begin
{cauta nodul cel mai apropiat de nodul curent si care nu a fost
marcat}
            minim:=1500;
            for j:=1 to 100 do
              if s[j] and (c[nod_curent,j]<=minim) then
                 begin
                nod_apropiat:=j; minim:=c[nod_curent,j];
                 end;
            s[nod_apropiat]:=false;
{ marcheaza nodul gasit ca fiind folosit }
            solutie[i]:=nod_apropiat; 
{ noteaza nodul gasit in vectorul solutie }
            nod_curent:=nod_apropiat; 
{ nodul gasit devine nod curent}
          end;
    maxim:=0; 
{cauta distanta maxima dintre doua puncte consecutive din
vectorul solutie }
    solutie[n+1]:=nc;
    pozitie:=1;
    for i:=1 to n do
       if c[solutie[i],solutie[i+1]]>maxim then
          begin
             maxim:=c[solutie[i],solutie[i+1]];
             pozitie:=i;
          end;
    maxim:=0; { maxim va contine drumul total }
    for i:=pozitie+1 to n do
       maxim:=maxim+10+c[solutie[i],solutie[i+1]];
    for i:=1 to pozitie-1 do
       maxim:=maxim+10+c[solutie[i],solutie[i+1]];
    if maxim<drum_minim then
      begin
         solutie_finala:=solutie; drum_minim:=maxim;
         poz_finala:=pozitie;
      end;
    end;
   writeln('Drum total : ',drum_minim:6:3);
   for i:=poz_finala+1 to n do 
    writeln(solutie_finala[i]:2,' - ',solutie_finala[i+1]:2,' 
',10+c[solutie_finala[i],solutie_finala[i+1]]:6:3);
   for i:=1 to poz_finala-1 do 
      writeln(solutie_finala[i]:2,' - ', solutie_finala[i+1]:2,' 
 ',10+c[solutie_finala[i],solutie_finala[i+1]]:6:3);
end.
-----------------------------------------------
Solutia 3:
uses crt;
type numar=array[1..101] of byte;
     punct=record
                 x,y:integer;
           end;
var c:array[1..100,1..100] of real;
    s:array[1..100] of boolean;
    solutie,solutie_finala:numar;
    drum_minim,minim,maxim:real;
    pozitie,poz_finala,nod_curent,nod_apropiat,nc,i,j,n:integer;

procedure citeste;
{ citeste datele de intrare din fisierul 'input50' }
var t:text;
    i,j:integer;
    coordonate:array[1..100] of punct;
begin
assign(t,'input50'); { datele se citesc din fisierul 'input50' }
reset(t);
readln(t,n);
for i:=1 to n do
    begin
    read(t,coordonate[i].x);
    readln(t,coordonate[i].y);
    end;
for i:=1 to n do   {Se determina matricea C a drumurilor}
  for j:=i+1 to n do
      begin
      c[i,j]:=sqrt(sqr(coordonate[i].x-coordonate[j].x)+
                   sqr(coordonate[i].y-coordonate[j].y));
      c[j,i]:=c[i,j];
      end;
close(t);
end;

function min(x,y:real):real;
begin
min:=y;
if y>x then min:=x;
end;

begin
clrscr;
citeste;
drum_minim:=1500;
for nc:=1 to n do
    begin
    nod_curent:=nc;
    for i:=1 to n do s[i]:=true;
    solutie[1]:=nod_curent;
    s[nod_curent]:=false;
    for i:=2 to n do
        begin
        { cauta nodul cel mai apropiat de nodul curent si care nu a fost marcat }
        minim:=1500;
        for j:=1 to 100 do
            if s[j] and (c[nod_curent,j]<=minim) then
               begin
               nod_apropiat:=j;
               minim:=c[nod_curent,j];
               end;
        s[nod_apropiat]:=false; { marcheaza nodul gasit ca fiind folosit }
        solutie[i]:=nod_apropiat; { noteaza nodul gasit in vectorul solutie }
        nod_curent:=nod_apropiat; { nodul gasit devine nod curent }
        end;
    maxim:=0; { cauta distanta maxima dintre doua puncte consecutive din vectorul solutie }
    solutie[n+1]:=nc;
    pozitie:=1;
    for i:=1 to n do
        if c[solutie[i],solutie[i+1]]>maxim then
           begin
           maxim:=c[solutie[i],solutie[i+1]];
           pozitie:=i;
           end;
    maxim:=0; { maxim va contine drumul total }
    for i:=pozitie+1 to n do maxim:=maxim+10+c[solutie[i],solutie[i+1]];
    for i:=1 to pozitie-1 do maxim:=maxim+10+c[solutie[i],solutie[i+1]];
    if maxim<drum_minim then
       begin
       solutie_finala:=solutie;
       drum_minim:=maxim;
       poz_finala:=pozitie;
       end;
    end;
writeln('Drum total : ',drum_minim:6:3);
for i:=poz_finala+1 to n do writeln(solutie_finala[i]:2,' - ', solutie_finala[i+1]:2,'   ',
                                 10+c[solutie_finala[i],solutie_finala[i+1]]:6:3);
for i:=1 to poz_finala-1 do writeln(solutie_finala[i]:2,' - ', solutie_finala[i+1]:2,'   ',
                                 10+c[solutie_finala[i],solutie_finala[i+1]]:6:3);
end.
--------------------------------------
